from collections import OrderedDict


class ListNode:

    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        return f"[ListNode: ]{self.val} next = {self.next} "


class TreeNode:

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __str__(self):
        return f"TreeNode({self.val})"


class LRUCache(object):

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            self.cache.move_to_end(key, last=False)
            return self.cache[key]

    def __str__(self):
        return f"LRUCache[{self.capacity}]: {self.cache}"

    def put(self, key: int, value: int) -> None:
        if len(self.cache) == self.capacity:
            if key not in self.cache:
                self.cache.popitem(last=True)
            self.cache[key] = value
            self.cache.move_to_end(key, last=False)
        else:
            self.cache[key] = value
            self.cache.move_to_end(key, last=False)


class TrieNode(object):

    def __init__(self):
        self.child = [None for i in range(26)]
        self.is_end = False

    def __str__(self):
        mesg = ""
        for idx, child in enumerate(self.child):
            if child is not None:
                mesg = f"idx = {idx} node = {str(child)}"
        return mesg


class Trie(object):

    def __init__(self):
        self.node = TrieNode()

    def __str__(self):
        return f"{str(self.node)}"

    def insert(self, word: str) -> None:
        node = self.node
        for ch in word:
            value = ord(ch) - ord('a')
            if node.child[value] is None:
                node.child[value] = TrieNode()
                node = node.child[value]
            else:
                node = node.child[value]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.node
        for ch in word:
            value = ord(ch) - ord('a')
            if node.child[value] is not None:
                node = node.child[value]
            else:
                node = None
                break
        if node is None:
            return False
        else:
            return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.node
        for ch in prefix:
            value = ord(ch) - ord('a')
            if node.child[value] is not None:
                node = node.child[value]
            else:
                node = None
                break
        return node is not None


# class Trie(object):

#     def __init__(self):
#         self.count = -1
#         self.has = [False for i in range(100)]
#         self.cache = [[-1 for i in range(26)] for i in range(100)]

#     def insert(self, word: str) -> None:
#         layer = 0
#         for ch in word:
#             value = ord(ch) - ord('a')
#             if self.cache[layer][value] == -1:
#                 self.cache[layer][value] = layer
#                 self.count += 1
#             layer += 1
#         self.has[value] = True

#     def search(self, word: str) -> bool:
#         layer = 0
#         for ch in word:
#             value = ord(ch) - ord('a')
#             if self.cache[layer][value] != -1:
#                 layer += 1
#             else:
#                 return False
#         return self.has[layer - 1]

#     def startsWith(self, prefix: str) -> bool:
#         layer = 0
#         for ch in prefix:
#             value = ord(ch) - ord('a')
#             if self.cache[layer][value] != -1:
#                 layer += 1
#         return layer == len(prefix)
